package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 45. 跳跃游戏 II
 * @date 2025/5/8 13:14
 */
public class E45 {

    /**
     * <h3>方法一：贪心算法，遍历时用一个变量统计能到达的最远距离，再用一个记录跳跃之前能到达的最远距离，在用一个变量记录跳跃次数</h3>
     *
     * @param nums nums
     * @return 跳跃次数
     */
    public int jump(int[] nums) {
        int jumps = 0, fathest = 0, currEnd = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            fathest = Math.max(fathest, nums[i] + i);
            // 如果到达了跳跃前的最远距离，则需要跳跃一次
            if (currEnd == i) {
                jumps++;
                currEnd = fathest;
            }
            if (currEnd > nums.length - 1) {
                break;
            }
        }
        return jumps;
    }
}
